package de.cau.apo.container;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;


public class BitIndexSet implements Collection<Integer> {

	final int n;
	final int[] data;
	
	int size = 0;
	
	public BitIndexSet(int n) {
		this.n = n;
		
		int cnt = n / Integer.SIZE;
		if (n % Integer.SIZE != 0)
			cnt++;
		this.data = new int[cnt];
	}
	
	private void checkElementRangeException(Integer e) {
		if (e == null)
			throw new NullPointerException("Null values are not allowed");
		if (e < 0 || e >= n) 
			throw new IllegalArgumentException("The elements to add must be between 0 and "+(n-1));
	}
	
	private boolean checkElementRangeBoolean(Integer e) {
		if (e == null || e < 0 || e >= n) 
			return false;
		return true;
	}
	
	private int getElementPos(Integer e) {
		return e / Integer.SIZE;
	}
	
	private int getElementOffset(Integer e) {
		return e % Integer.SIZE;
	}
	
	private int countElements(int dataEntry) {
		int cnt = 0;
		while (dataEntry != 0) {
			cnt += dataEntry &= 1;
			dataEntry >>>= 1;
		}
		return cnt;
	}
	
	@Override
	public boolean add(Integer e) {
		checkElementRangeException(e);
		if (contains(e)) return false;
		
		int mask = 1 << getElementOffset(e); // create bit mask with a 1 at position i%8
		data[getElementPos(e)] |= mask;
		size++;
		return true;
	}

	@Override
	public boolean addAll(Collection<? extends Integer> c) {
		if (c instanceof BitIndexSet) {
			return addAll((BitIndexSet) c);
		}
		for (Integer e : c)
			checkElementRangeException(e);
		boolean result = false; 
		for (Integer e : c) {
			result = add(e) || result;
		}
		return result;
	}
	
	public boolean addAll(BitIndexSet c) {
		boolean result = false;
		for (int i = 0; i < data.length && i < c.data.length; i++) {
			int delta = ~data[i] & c.data[i];
			result = delta != 0 || result;
			size += countElements(delta);
			data[i] |= c.data[i];
		}
		return result;
	}

	@Override
	public void clear() {
		for (int i = 0; i < data.length; i++)
			data[i] &= 0;
	}

	@Override
	public boolean contains(Object o) {
		if (!(o instanceof Integer)) return false;
		Integer e = (Integer) o;
		if (!checkElementRangeBoolean(e)) return false;
		int mask = 1 << getElementOffset(e); // create bit mask with a 1 at position i%8
		return (data[getElementPos(e)] & mask) > 0;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		if (c instanceof BitIndexSet) {
			return containsAll((BitIndexSet) c);
		}
		for (Object o : c) {
			if (!contains(o)) return false;
		}
		return true;
	}

	public boolean containsAll(BitIndexSet c) {
		int i;
		for (i = 0; i < data.length && i < c.data.length; i++) {
			if ((~data[i] & c.data[i]) != 0) return false;
		}
		return i <= c.data.length;
	}
	
	@Override
	public boolean isEmpty() {
		for (int i = 0; i < data.length; i++)
			if (data[i] != 0) return false;
		return true;
	}

	@Override
	public Iterator<Integer> iterator() {
		return new BitIndexSetIterator();
	}

	@Override
	public boolean remove(Object o) {
		if (!(o instanceof Integer)) return false;
		Integer e = (Integer) o;
		if (!checkElementRangeBoolean(e)) return false;
		if (!contains(e)) return false;
		int mask = ~(1 << getElementOffset(e)); // create bit mask with everywhere 1 except at position i%8
		data[getElementPos(e)] &= mask;
		size--;
		return true;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		if (c instanceof BitIndexSet) {
			return removeAll((BitIndexSet) c);
		}
		boolean result = false;
		for (Object o : c) {
			result = remove(o) || result;
		}
		return result;
	}
	
	public boolean removeAll(BitIndexSet c) {
		boolean result = false;
		for (int i = 0; i < data.length && i < c.data.length; i++) {
			int delta = data[i] & c.data[i];
			result = delta != 0 || result; 
			size -= countElements(delta);
			data[i] &= ~c.data[i];
		}
		return result;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		if (c instanceof BitIndexSet) {
			return retainAll((BitIndexSet) c);
		}
		BitIndexSet notContainedElements = new BitIndexSet(this.n);
		for (Integer e : this) {
			if (!c.contains(e))
				notContainedElements.add(e);
		}
		return removeAll(notContainedElements);
	}
	
	public boolean retainAll(BitIndexSet c) {
		boolean result = false;
		int i;
		for (i = 0; i < data.length && i < c.data.length; i++) {
			int delta = data[i] & ~c.data[i];
			result = delta != 0 || result; 
			size -= countElements(delta);
			data[i] &= c.data[i];
		}
		for (; i < data.length; i++) {
			result = data[i] != 0 || result;
			size -= countElements(data[i]);
			data[i] &= 0;
		}
		return result;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public Object[] toArray() {
		Object[] ar = new Object[this.size];
		int i = 0;
		// set collection elements in array
		for (Integer e : this) {
			ar[i++] = e;
		}
		return ar;
	}

	@SuppressWarnings("unchecked")
	@Override
	public <T> T[] toArray(T[] a) {
		T[] ar = a;
		// instantiate new array if specified array is too small
		if (a.length < this.size)
			ar = Arrays.copyOf(a, this.size);
		int i = 0;
		// set collection elements in array
		for (Integer e : this)
			try {
				ar[i++] = (T) e;
			} catch (ClassCastException ex) {
				throw new ArrayStoreException("Specified array type does not fit to the type Integer");
			}
		// set following entry to null if original array was too long
		if (i < a.length) 
			ar[i] = null;
		return null;
	}
	
	// ######### iterator class #########
	
	public class BitIndexSetIterator implements Iterator<Integer> {

		int lastItem = -1;
		boolean removed = false;
		
		@Override
		public boolean hasNext() {
			int dataPos = lastItem == -1 ? 0 : getElementPos(lastItem + 1);
			int mask = lastItem != -1 ? -1 << getElementOffset(lastItem + 1) : -1;
			while ((mask & data[dataPos]) == 0 && dataPos < data.length) {
				dataPos++;
				mask = -1;
			}
			return dataPos < data.length;
		}

		@Override
		public Integer next() {
			int dataPos = lastItem == -1 ? 0 : getElementPos(lastItem + 1);
			int mask = lastItem != -1 ? -1 << getElementOffset(lastItem + 1) : -1;
			while ((mask & data[dataPos]) == 0 && dataPos < data.length) {
				dataPos++;
				mask = -1;
			}
			if (dataPos >= data.length) 
				throw new NoSuchElementException("The iteration has no more elements.");
			
			mask = 1;
			int i = 0;
			if (lastItem != -1) {
				i = getElementOffset(lastItem + 1);
				mask = 1 << i;
			}
			for (; i < Integer.SIZE; i++) {
				if ((mask & data[dataPos]) != 0) {
					removed = false;
					lastItem = dataPos * Integer.SIZE + i;
					return lastItem;
				}
				mask = mask << 1;
			}
			throw new NoSuchElementException("The iteration has no more elements.");
		}

		@Override
		public void remove() {
			if (removed || lastItem == -1)
				throw new IllegalStateException("No element there to remove.");
			
			BitIndexSet.this.remove(lastItem);
			removed = true;
		}
		
	}

}
